package lc;

import java.util.Arrays;

import org.junit.Test;

public class Ex576 {
    class Solution {
        public int findPaths(int m, int n, int maxMove, int startRow, int startColumn) {
            //(i, j)位于边界，则f[i][j][1] = 1;
            int[][][] f = new int[m][n][maxMove + 1];
            int mod = (int)1e9 + 7;

            for (int cur = 1; cur <= maxMove; cur++) {
                for (int i = 0; i < m; i++) {
                    for (int j = 0; j < n; j++) {
                        if (i == 0) {
                            f[i][j][cur] += 1;
                        }
                        if (i == m - 1) {
                            f[i][j][cur] += 1;
                        }
                        if (j == 0) {
                            f[i][j][cur] += 1;
                        }
                        if (j == n - 1) {
                            f[i][j][cur] += 1;
                        }
                        if (cur != 1) {
                            if (i > 0) {
                                f[i][j][cur] += f[i - 1][j][cur - 1];
                                f[i][j][cur] %= mod;
                            }
                            if (i < m - 1) {
                                f[i][j][cur] += f[i + 1][j][cur - 1];
                                f[i][j][cur] %= mod;
                            }
                            if (j > 0) {
                                f[i][j][cur] += f[i][j - 1][cur - 1];
                                f[i][j][cur] %= mod;
                            }
                            if (j < n - 1) {
                                f[i][j][cur] += f[i][j + 1][cur - 1];
                                f[i][j][cur] %= mod;
                            }
                        }
                    }
                }
            }

            return f[startRow][startColumn][maxMove];
        }
    }

    @Test
    public void test() {
        Solution s = new Solution();
        Solution1 s1 = new Solution1();

        int res = s1.findPaths(8,24,23,5,22);
        System.out.println(res);
    }

    class Solution1 {
        int m, n;
        int[][][] f;
        public int findPaths(int m, int n, int maxMove, int startRow, int startColumn) {
            if (maxMove == 0) return 0;
            //(i, j)位于边界，则f[i][j][1] = 1;
            this.m = m;
            this.n = n;
            f = new int[m][n][maxMove + 1];
            for (int i = 0; i < m; i++) {
                for (int j = 0; j < n; j++) {
                    Arrays.fill(f[i][j], -1);
                }
            }
            dfs(startRow, startColumn, maxMove);
            return f[startRow][startColumn][maxMove];
        }

        int mod = (int)1e9+7;

        public int dfs(int i, int j, int cur) {
            if (f[i][j][cur] >= 0) {
                return f[i][j][cur];
            }
            if (cur == 1) {
                if (i == 0 || i == m - 1 || j == 0 || j == n - 1) {
                    f[i][j][cur] = 0;
                    if (i == 0) {
                        f[i][j][cur] += 1;
                    }
                    if (i == m - 1) {
                        f[i][j][cur] += 1;
                    }
                    if (j == 0) {
                        f[i][j][cur] += 1;
                    }
                    if (j == n - 1) {
                        f[i][j][cur] += 1;
                    }
                } else {
                    f[i][j][cur] = 0;
                }
                return f[i][j][cur];
            }
            //若处于边缘，可以向着界外走,此时得到一个路径，或者向着其他方向走
            int up = i == 0 ? 1 : dfs(i - 1, j, cur - 1);
            int down = i == m - 1 ? 1 : dfs(i + 1, j, cur - 1);
            int left = j == 0 ? 1 : dfs(i, j - 1, cur - 1);
            int right = j == n - 1 ? 1 : dfs(i, j + 1, cur - 1);
            f[i][j][cur] = (up + down + left + right) % mod;
            return f[i][j][cur];
        }
    }
}


 